Merge sorted array

Time: O(N); Space: O(1); easy

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Example 1:

Input: A = [1,2,3,0,0,0], m = 3; B = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

Notes:

  • You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B.

  • The number of elements initialized in A and B are m and n respectively.

[1]:

class Solution1(object):
    def merge(self, A, m, B, n):
        '''
        :type A: List[int]
        :type m: int  # length of A
        :type B: List[int]
        :type n: int  # length of B
        :rtype: Do not return anything, modify nums in-place instead.
        '''
        last, i, j = m + n - 1, m - 1, n - 1

        while i >= 0 and j >= 0:
            if A[i] > B[j]:
                A[last] = A[i]
                last, i = last - 1, i - 1
            else:
                A[last] = B[j]
                last, j = last - 1, j - 1

        while j >= 0:
                A[last] = B[j]
                last, j = last - 1, j - 1

[6]:

s = Solution1()
A = [1,2,3,0,0,0]
m = 3
B = [2,5,6]
n = 3
s.merge(A, m, B, n)
assert A == [1, 2, 2, 3, 5, 6]

A = [1, 3, 5, 0, 0, 0, 0]
m = 3
B = [2, 4, 6, 7]
n = 4
s.merge(A, m, B, n)
assert A == [1, 2, 3, 4, 5, 6, 7]